package com.startrek.ch02;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
    }

    public boolean find(int val) {
        if (root == null)
            return false;

        TreeNode currNode = root;
        while (currNode != null) {
            if (val == currNode.val) {
                return true;
            } else if (val < currNode.val) {
                currNode = currNode.leftNode;
            } else {
                currNode = currNode.rightNode;
            }
        }

        return false;
    }

    public void insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }

        if (find(val)) {
            throw new IllegalArgumentException("Cannot insert dup values!");
        }

        TreeNode currNode = root;
        while (currNode != null) {
            if (val < currNode.val) {
                if (currNode.leftNode == null) {
                    currNode.leftNode = new TreeNode(val);
                    return;
                }
                currNode = currNode.leftNode;
            } else {
                if (currNode.rightNode == null) {
                    currNode.rightNode = new TreeNode(val);
                    return;
                }
                currNode = currNode.rightNode;
            }
        }
    }

    /*
    To convert an inherently recursive procedures to iterative, we need an explicit stack.
    Following is a simple stack based iterative process to print Preorder traversal.
    1) Create an empty stack nodeStack and push root node to stack.
    2) Do following while nodeStack is not empty.
        ….a) Pop an item from stack and print it.
        ….b) Push right child of popped item to stack
        ….c) Push left child of popped item to stack
    Right child is pushed before left child to make sure that left subtree is processed first.
     */
    public List<Integer> preorderNonRecursive() {
        Stack<TreeNode> nodeStack = new Stack<>();
        nodeStack.push(root);
        List<Integer> list = new ArrayList<>();
        while (!nodeStack.isEmpty()) {
            TreeNode currNode = nodeStack.pop();
            list.add(currNode.val);
            if (currNode.rightNode != null) {
                nodeStack.push(currNode.rightNode);
            }
            if (currNode.leftNode != null) {
                nodeStack.push(currNode.leftNode);
            }
        }

        return list;
    }

    public List<Integer> preorderRecursive() {
        List<Integer> list = new ArrayList<>();
        preorderRecursive(root, list);

        return list;
    }

    private void preorderRecursive(TreeNode node, List<Integer> list) {
        if (node == null)
            return;

        list.add(node.val);
        preorderRecursive(node.leftNode, list);
        preorderRecursive(node.rightNode, list);
    }


    /*
    1) Create an empty stack S.
    2) Initialize current node as root
    3) Push the current node to S and set current = current->left until current is NULL
    4) If current is NULL and stack is not empty then
        a) Pop the top item from stack.
        b) Print the popped item, set current = popped_item->right
        c) Go to step 3.
    5) If current is NULL and stack is empty then we are done.
     */
    public List<Integer> inorderNonRecursive() {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> nodeStack = new Stack<>();
        TreeNode currNode = root;
        while (currNode != null || !nodeStack.isEmpty()) {
            while (currNode != null) {
                nodeStack.push(currNode);
                currNode = currNode.leftNode;
            }
            currNode = nodeStack.pop();
            list.add(currNode.val);
            currNode = currNode.rightNode;
        }

        return list;
    }

    public List<Integer> inorderRecursive() {
        List<Integer> list = new ArrayList<>();
        inorderRecursive(root, list);

        return list;
    }

    private void inorderRecursive(TreeNode node, List<Integer> list) {
        if (node == null)
            return;

        inorderRecursive(node.leftNode, list);
        list.add(node.val);
        inorderRecursive(node.rightNode, list);
    }

    public List<Integer> postorderNonRecursive() {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty()) {
            TreeNode temp = s1.pop();
            s2.push(temp);
            if (temp.leftNode != null)
                s1.push(temp.leftNode);
            if (temp.rightNode != null)
                s1.push(temp.rightNode);
        }
        while (!s2.isEmpty()) {
            TreeNode temp = s2.pop();
            list.add(temp.val);
        }

        return list;
    }

    public List<Integer> postorderRecursive() {
        List<Integer> list = new ArrayList<>();
        postorderRecursive(root, list);

        return list;
    }

    private void postorderRecursive(TreeNode node, List<Integer> list) {
        if (node == null)
            return;

        postorderRecursive(node.leftNode, list);
        postorderRecursive(node.rightNode, list);
        list.add(node.val);
    }
}

class TreeNode {
    int val;
    TreeNode leftNode;
    TreeNode rightNode;

    TreeNode(int val) {
        this.val = val;
    }
}
